package com.atguigu.tree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        HeroNode node1 = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "关胜");

        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        tree.setRoot(node1);
        System.out.println("前序遍历");
        tree.preOrder();
        System.out.println("中序遍历");
        tree.infixOrder();
        System.out.println("后序遍历");
        tree.postOrder();
        System.out.println("前序查找");
        HeroNode resnode = tree.preOrderSearch(5);
        if(resnode!=null){
            System.out.printf("找到了，信息为no=%d,name=%s",resnode.getNo(),resnode.getName());
        }else{
            System.out.println("没有找到");
        }
        System.out.println("中序查找");
        HeroNode resnode_2 = tree.infixOrderSearch(5);
        if(resnode_2!=null){
            System.out.printf("找到了，信息为no=%d,name=%s",resnode_2.getNo(),resnode_2.getName());
        }else{
            System.out.println("没有找到");
        }
        System.out.println("后序查找");
        HeroNode resnode_3 = tree.postOrderSearch(5);
        if(resnode_3!=null){
            System.out.printf("找到了，信息为no=%d,name=%s",resnode_3.getNo(),resnode_3.getName());
        }else{
            System.out.println("没有找到");
        }
        System.out.println("删除节点");
        System.out.println("删除前");
        tree.preOrder();
        System.out.println("删除后");
        tree.deleteNode(3);
        tree.preOrder();




    }
}
class BinaryTree{
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }
    //删除节点
    public void deleteNode(int no){
        if(root!=null){
            if(root.getNo()==no){
                root=null;
            }else{
                root.deleteNode(no);
            }
        }else{
            System.out.println("二叉树为空树");
        }
    }
    //前序遍历
    public void preOrder(){
        if(this.root!=null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //中序遍历
    public void infixOrder(){
        if(this.root!=null){
            this.root.infixOrder();
        }else{
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //后续遍历
    public void postOrder(){
        if(this.root!=null){
            this.root.postOrder();
        }else{
            System.out.println("二叉树为空，无法遍历");
        }
    }

    //前序查找
    public HeroNode preOrderSearch(int no){
        if(root!=null){
            return root.preOrderSearch(no);
        }else{
            System.out.println("二叉树为空");
            return null;
        }
    }
    //中序查找
    public HeroNode infixOrderSearch(int no){
        if(root!=null){
            return root.infixOrderSearch(no);
        }else{
            System.out.println("二叉树为空");
            return null;
        }
    }
    //后续查找
    public HeroNode postOrderSearch(int no){
        if(root!=null){
            return root.postOrderSearch(no);
        }else{
            System.out.println("二叉树为空");
            return null;
        }
    }

}
//创建节点
class HeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //递归删除节点
    /*
    * 如果删除的是叶子节点，则删除叶子节点
    * 如果删除的是非叶子节点，则删除该子树
    * */
    public void deleteNode(int no){
        if(this.left!=null&&this.left.no==no){
            this.left=null;
            return;
        }
        if(this.right!=null&&this.right.no==no){
            this.right=null;
            return;
        }
        if(this.left!=null){
            this.left.deleteNode(no);
        }
        if(this.right!=null){
            this.right.deleteNode(no);
        }



    }
    /*
     * 分析二叉树的前中后序遍历
     * 1 传创建一颗二叉树
     * 2 前序遍历
     *   2.1 先输出当前节点（父节点）
     *   2.2 如果左节点不为空，则递归继续前序遍历
     *   2.2 如果右节点不为空，则递归继续谦虚遍历
     * 3 中序遍历
     *   3.1 如果当前节点的左节点不为空，则递归中序遍历
     *   3.2 输出当前父节点
     *   3.3 如果当前节点的右节点不为空，则递归中序遍历
     * 4 后序遍历
     *   4.1 如果当前节点的左节点不为空，则递归中序遍历
     *   4.2 如果当前节点的右节点不为空，则递归中序遍历前序遍历
     *   4.3 输出当前父节点
     */
    //前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }

    }

    //中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
    //后续遍历
    public void postOrder(){
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }
    /*
     * 使用前中后序查找指定的节点：
     * 使用前序查找的思路：
     *   1先判断当前节点的no是否为要查找的
     *   2如果相等，则返回当前节点
     *   3如果不相等，则判断当前节点的左节点是否为空，如果不为空，则递归前序查找
     *   4如果左递归前序查找，找到该节点，则返回，否则继续判断，当前节点的右子节
     *   点是否为空，如果不为空，则继续右递归前序查找。
     *使用中序查找的思路
     *   1判断当前节点的左节点是否为空，如果不为空，则递归中序查找
     *   2如果找到该节点，则返回；如果没有找到该节点，就和当前节点进行比较，如果是，则返回当前节点，否则继续进行
     *   右递归的中序查找
     *   3如果右递归中序查找，找到就返回，否则返回null
     * 使用后续查找的思路
     *   1判断当前节点的左节点是否为空，如果不为空，则递归后序查找
     *   2如果找到，返回；如果没有找到，就判断当前节点的右子节点是否为空，如果不为空，则右递归进行后序查找，如果找到就返回
     *   3.和当前节点进行比较，如果是则返回，否则返回null。
     *
     *
     * */
    //前序查找

    public HeroNode preOrderSearch(int no){
        System.out.println("前序查找");
//        1先判断当前节点的no是否为要查找的
//        2如果相等，则返回当前节点
        if (this.no==no){
            return this;
        }
        //3如果不相等，则判断当前节点的左节点是否为空，如果不为空，则递归前序查找
        //如果找到该节点，则返回
        HeroNode resNode=null;
        if (this.left!=null){
            resNode=this.left.preOrderSearch(no);
        }
        if(resNode!=null){//说明在左子树找到了
            return resNode;
        }
        //继续判断，当前节点的右子节点点是否为空，如果不为空，则继续右递归前序查找。
        if(this.right!=null){
            resNode=this.right.preOrderSearch(no);
        }
        return resNode;
    }
    //中序查找
    public HeroNode infixOrderSearch(int no){
        /*
        * *使用中序查找的思路
         *   1判断当前节点的左节点是否为空，如果不为空，则递归中序查找
         *   2如果找到该节点，则返回；如果没有找到该节点，就和当前节点进行比较，如果是，则返回当前节点，否则继续进行
         *   右递归的中序查找
         *   3如果右递归中序查找，找到就返回，否则返回null
        * */

        HeroNode resNode=null;
        if(this.left!=null){
            resNode=this.left.infixOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        System.out.println("中序查找");
        if(this.no==no){
            return this;
        }
        if(this.right!=null){
            resNode=this.right.infixOrderSearch(no);
        }
        return resNode;

    }
    //后续查找
    public HeroNode postOrderSearch(int no){

       /* 使用后续查找的思路
          1判断当前节点的左节点是否为空，如果不为空，则递归后序查找
          2如果找到，返回；如果没有找到，就判断当前节点的右子节点是否为空，如果不为空，则右递归进行后序查找，如果找到就返回
          3和当前节点进行比较，如果是则返回，否则返回null。*/
        HeroNode resNode=null;
        if(this.left!=null){
            resNode=this.left.postOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        if(this.right!=null){
            resNode=this.right.postOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        System.out.println("后序查找");
        if(this.no==no){
            return this;

        }
        return null;
    }
}
